Resolution, heavy width and pseudorandom generators

Abstract: Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson we call a pseudorandom generator hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement that $b$ is outside of the image for any string $b \in \{0, 1\}^m$. In ABRW04 the authors suggested the "functional encoding" of the considered statement for Nisan-Wigderson generator that allows the introduction of "local" extension variables and gave a lower bound on the length of Resolution proofs if the number of extension variables is bounded by the $n^2$ (where $n$ is the number of inputs of the PRG).

In this talk, we discuss a "heavy width" measure for Resolution that allows us to show a lower bound on the length of Resolution proofs of the considered statement for the Nisan-Wigderson generator with a superpolynomial number of local extension variables. It is a solution to one of the open problems from ABRW04.

computational complexitylogic

Audience: researchers in the topic

IM CAS logic seminar